/*
 * @lc app=leetcode.cn id=78 lang=cpp
 *
 * [78] 子集
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        n = nums.size();
        vector<vector<int>> res;

        int resNum = 1;
        for (int i=0;i<n;++i){
            resNum <<= 1;
        }

        // res is a full bin tree !!!
        // let's use array as heep ~
        res.resize(resNum);

        int mod = resNum;
        int nextMod = mod / 2;
        for (int i=0;i<n;++i){

            for (int j=0;j<resNum;++j){
// printf("j %d : %d - %d\n", j, j%mod, nextMod);
                if (j%mod < nextMod){
                    res[j].push_back(nums[i]);
                }
            }

            mod = nextMod;
            nextMod = mod / 2;
// printf("mod %d next mod %d\n", mod, nextMod);
        }

        return res;
    }
private:
    int n;
};
// @lc code=end

